|
In computer science, more specifically computational complexity theory, ''Computers and Intractability: A Guide to the Theory of NP-Completeness'' is an influential textbook by Michael Garey and David S. Johnson. It was the first book exclusively on the theory of NP-completeness and computational intractability. The book features an appendix providing a thorough compendium of NP-complete problems (which was updated in later printings of the book). The book is now outdated in some respects as it does not cover more recent development such as the PCP theorem. It is nevertheless still in print and is regarded as a classic: in a 2006 study, the CiteSeer search engine listed the book as the most cited reference in computer science literature.〔(【引用サイトリンク】title=Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity) )〕 ==Open problems== Another appendix of the book featured problems for which it was not known whether they were NP-complete or in P (or neither). The problems (with their original names) are: # Graph isomorphism # Subgraph homeomorphism (for a fixed graph ''H'') # Graph genus # Chordal graph completion # Chromatic index〔''NP''-complete: 〕 # Spanning tree parity problem〔In ''P'': 〕 # Partial order dimension # Precedence constrained 3-processor scheduling # Linear programming # Total unimodularity〔In ''P'': 〕 # Composite number #:Testing for compositeness is known to be in ''P'', but the complexity of the closely related integer factorization problem remains open. # Minimum length triangulation〔Is ''NP''-hard: 〕 As of 2015, only problem 1 has yet to be classified. Problem 12 is known to be ''NP''-hard, but it is unknown if it is in ''NP''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Computers and Intractability」の詳細全文を読む スポンサード リンク
|